/*
 ============================================================================
 Name        : ParallelDominatingSub.c
 Author      : Štěpán Ort a Michal Havlíček
 Version     : 0.1
 ============================================================================
 */
#define VERBOSE 					true
#define SLOWDOWN					false

#define CHECK_MSG_AMOUNT  			100

#define TAG_NEW_DIMENSION			1
#define TAG_WORK_REQUEST 			2
#define TAG_WORK_SENT    			3
#define TAG_WORK_SIZE_SENT			4
#define TAG_WORK_NOWORK  			5
#define TAG_SMALLEST_SUB    		6
#define TAG_BEST_REQUEST   			7
#define TAG_BEST_SENT   			8
#define TAG_TOKEN_CYRCLE			9
#define TAG_FINISH					10
#define TAG_DONT_HAVE_BEST			11

#define TOKEN_START					1
#define TOKEN_WHITE					2
#define TOKEN_BLACK					3

#include "mpi.h" 
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <memory>
#include <set>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <unistd.h>

using namespace std;

struct Graph{
	/** @var pocet uzlu grafu */
	int size;
	/** @var matice sousednosti */
	vector< vector<bool> > matrix;
	vector< set<int> > neighbourhoodMap;
};

/**
 * Funkce expanduje castecne reseni(vraci potomky tohoto reseni).
 * Nove castecne reseni se sklada z castecneho reseni,
 * ktere je doplnene o nove prvky, ktere puvodni neobsahovalo.
 *
 * @param partialResult Castecne reseni, ktere rozsirujeme o nove prvky
 * @param graph Definice grafu
 * @return Vraci nova castecna reseni
 */
vector< vector<int> > expandPartialResult(vector<int> partialResult, Graph *graph) {
	int max = 0;
	//najdi maximalni prvek v castecnem reseni
	for (int i = 0; i < partialResult.size(); i++) {
		if (partialResult[i] > max) {
			max = partialResult[i];
		}
	}
	//vysledek
	vector < vector<int> > expandedResults(graph->size - (max + 1));
	//dopln castecne reseni o nove prvky
	for (int i = max + 1; i < graph->size; i++) {
		//cout << "roziruji o:" << i << endl;
		vector<int> expandedPartialResult = partialResult;
		expandedPartialResult.push_back(i);
		expandedResults[i - (max + 1)] = expandedPartialResult;
	}

	return expandedResults;
}

/**
 * Rozsiri zasobnik o nova castecna reseni.
 *
 * @param expandedPartialResult Rozsirene castecne reseni
 * @param stack Reference na globalni zasobnik
 */
void expandStack(vector< vector<int> > expandedPartialResult, vector< vector<int> >& stack) {
	for (int i = 0; i < expandedPartialResult.size(); i++) {
		stack.push_back(expandedPartialResult[i]);
	}
}
void divideStackSimple(vector< vector<int> >*stack, vector< vector<int> > *newStack ) {
	int originalSize = stack->size();
	for (int var = 0; var < originalSize/2; ++var) {
		newStack->push_back(stack->back());
		stack->pop_back();
	}
}
void divideStack(vector< vector<int> >*stack, vector< vector<int> > *newStack ) {

	vector< vector<int> > firstHalf(0, vector<int>(1, 0));
	vector< vector<int> > secondHalf(0, vector<int>(1, 0));

	int i = stack->size() -1;
	//iteruj skrz zasobnik
	while(i >= 0){
		int size = stack[i].size();
		//spocitej kolik polozek lze obetovat
		int diff = 0;
		if(size > 1){
			diff = (int)floor((((float)stack->at(i).at(size-1) - stack->at(i).at(size-2))/2));
		}else{
			diff = (int)floor(((float)stack->at(i).at(0))/2);
		}
		//rozdel na pul
		for(int j = 0; j < diff; j++){
			//printVector(stack[i--],"Adding vector to second half:");
			secondHalf.insert(secondHalf.begin(), stack->at(i--));
		}
		while(size == stack->at(i).size() && i >= 0){
			//printVector(stack[i--],"Adding vector to first half:");
			firstHalf.insert(firstHalf.begin(),stack->at(i--));
		}
	}
	//prvni polovina patri lokalnimu zasobniku
	*stack = firstHalf;
	//druha polovina patri odesilanemu zasobniku
	*newStack = secondHalf;
}

void exploreNeighbourhood(set<int> *neighbourhood, Graph *graph, int node, int currentLevel) {
	if (currentLevel > 1) {
		for (int var = 0; var < graph->size; ++var) {
			if (graph->matrix[node][var])
			{
				exploreNeighbourhood(neighbourhood, graph, var, currentLevel - 1);
			}
		}

	}
	neighbourhood->insert(node);
}

bool testPartialResult(vector<int> partialResult, Graph *graph, int level) {
	bool ok[graph->size];
	for (int i = 0; i < partialResult.size(); ++i) {
		if (graph->neighbourhoodMap[partialResult[i]].empty()) {
			set<int> neighbourhood;
			exploreNeighbourhood(&neighbourhood, graph, partialResult[i], level);
			graph->neighbourhoodMap[partialResult[i]] = neighbourhood;
		}
		set<int>::iterator theIterator;
		for( theIterator = graph->neighbourhoodMap[partialResult[i]].begin(); theIterator != graph->neighbourhoodMap[partialResult[i]].end(); theIterator++ ) {
			ok[*theIterator] = true;
		}
	}
	for (int k = 0; k < graph->size; ++k) {
		if (!ok[k]) return false;
	}
	return true;
}

void printVector(vector<int> print, string message, int rank) {
	cout << rank << ": " << message << "(";
	for (int i = 0; i < print.size() - 1; i++) {
		cout << print[i] << ", ";
	}
	cout << print[print.size()-1] << ")\n";
}

bool loadGraph(char fileName[], Graph *graph)
{
	string line;
	ifstream myfile (fileName);
	if (myfile.is_open())
	{
		getline(myfile, line);
		int graphSize = atoi(line.c_str());
		vector< vector<bool> > matrix(graphSize, vector<bool>(graphSize, false));
		vector< set<int> > neighbourhoodMap(graphSize);
		int i = 0;
		for (int var = 0; var < graphSize; ++var)
		{
			getline (myfile,line);
			for(int j = 0; j < graphSize; ++j) {
				if(line[j] == '1')	{
					matrix[i][j] = true;
				}
			}
			i++;
		}
		graph->size = graphSize;
		graph->matrix = matrix;
		graph->neighbourhoodMap = neighbourhoodMap;
		myfile.close();
		return true;
	}
	return false;
}

bool init(int *argc, char **argv, Graph *graph, int *level) {
	if (*argc ==3) {
		char* fileName = argv[*argc - 2];
		if (!loadGraph(fileName, graph)) {
			std::cout << "Graph file is not valid!\n";
			return false;
		}

		int l = atoi(argv[*argc - 1]);
		if (l > 0) {
			*level = l;
		} else {
			std::cout << "i-value is not valid!\n";
			return false;
		}
	}
	else {
		return false;
	}
	return true;
}

void initStack(vector< vector<int> > *stack, int size, int p, int my_rank) {
	for (int var = 0; var < size; ++var) {
		if ((var % p) == my_rank) {
			vector<int> vec(1, var);
			stack->push_back(vec);
		}
	}
}


void arrayToStack(vector< vector<int> > *stack, int *array, int arraySize) {
	int i = 0;
	while (i < arraySize) {
		int vecSize = array[i];
		vector<int> vec(vecSize);
		i++;
		for (int var = 0; var < vecSize; ++var) {
			vec.push_back(array[i]);
			i++;
		}
	}
}

int stackToArray(vector< vector<int> > *stack, int* array) {
	int sumSize = stack->size();
	for (int var = 0; var < stack->size(); ++var) {
		sumSize += stack->at(var).size();
	}
	int a[sumSize];

	int i = 0;
	for (int j = 0; j < stack->size(); ++j) {
		a[i] = stack->at(j).size();
		i++;
		for (int k = 0; k < stack->at(j).size(); ++k) {
			a[i] = stack->at(j).at(k);
			i++;
		}

	}
	array = a;
	return sumSize;
}

void sendToken(int *my_rank, int *p) {
	if (*p >= 2) {
		int token;
		if (*my_rank == 0) {
			cout << *my_rank << ": Sending token\n";
			int token = TOKEN_WHITE;
			MPI_Send(&token,1, MPI_INT, 1, TAG_TOKEN_CYRCLE, MPI_COMM_WORLD);
		}
		else {
			cout << *my_rank << ": Sending request to send token\n";
			token = TOKEN_START;
			MPI_Send(&token, 1, MPI_INT, 0, TAG_TOKEN_CYRCLE, MPI_COMM_WORLD);
		}
	}
}

bool checkMessages(vector< vector<int> > *stack, Graph *graph, int *dimension, int *my_rank, int *p) {
	if (*p == 1)
	{
		return true;
	}

	if (stack->size()==0) {
		sendToken(my_rank, p);
	}

	cout << *my_rank << ": Checking messages\n";
	int flag;
	do {
		flag = 0;
		MPI_Status  status;
		MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);
		if (flag) {
			int source = status.MPI_SOURCE;
			int tag = status.MPI_TAG;
			cout << *my_rank << ": Message recieved tag=" << tag << " from=" << source << "\n";
			switch (tag)
			{
			case TAG_NEW_DIMENSION:
				int oldDimension;
				oldDimension = *dimension;
				int newDimension;
				MPI_Recv(&newDimension, 1, MPI_INT, source, TAG_NEW_DIMENSION, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
				cout << *my_rank << ": Dimension update resieved: old=" << oldDimension << " new=" << newDimension << "\n";
				*dimension = newDimension;
				break;
			case TAG_WORK_REQUEST:
				MPI_Recv(0, 0, MPI_INT, source, TAG_WORK_REQUEST, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
				cout << *my_rank << ": Work request recieved\n";
				//Pokud bych práci dokončil během dalšího cyklu, budu tvrdit, že už žádnou nemám
				if (stack->size() >= 2) {
					cout << *my_rank << ": Will share work\n";
					vector< vector<int> > stackToSend;
					cout << *my_rank << ": Will divide  size=" << stack->size() << "\n";
					divideStack(stack, &stackToSend);
					cout << *my_rank << ": Divided stack (stack size=" << stack->size() << ", stack to send size=" << stackToSend.size() << ")\n";
					int* array;
					int arraySize = stackToArray(&stackToSend, array);
					cout << *my_rank << ": Sending stack size\n";
					MPI_Ssend(&arraySize, 1, MPI_INT, source, TAG_WORK_SIZE_SENT, MPI_COMM_WORLD);
					cout << *my_rank << ": Sending stack\n";
					MPI_Ssend(&array, arraySize, MPI_INT, source, TAG_WORK_SENT, MPI_COMM_WORLD);
				}
				else {
					cout << *my_rank << ": Pretends that has no work\n";
					MPI_Send(0,0,MPI_INT,source, TAG_WORK_NOWORK, MPI_COMM_WORLD);
				}
				break;
			case TAG_WORK_SIZE_SENT:
				//Přijmutí velikosti zprávy
				int arraySize;
				MPI_Recv(&arraySize, 1, MPI_INT, source, TAG_WORK_SIZE_SENT, MPI_COMM_WORLD, &status);
				int *array;
				MPI_Recv(array, arraySize, MPI_INT, source, TAG_WORK_SENT, MPI_COMM_WORLD, &status);
				arrayToStack(stack, array, arraySize);
				return false;
				break;
			case TAG_WORK_SENT:
				cout << "INVALID TAG!";
				break;
			case TAG_WORK_NOWORK :
				MPI_Recv(0, 0, MPI_INT, source, TAG_WORK_NOWORK, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
				cout << *my_rank << ": proc=" << source << " has no work\n";
				int next;
				next = (source + 1) % *p;
				if (next != *my_rank) {
					MPI_Send(0, 0, MPI_INT, next, TAG_WORK_REQUEST, MPI_COMM_WORLD);
				}
				break;
			case TAG_TOKEN_CYRCLE:
				int token;
				MPI_Recv(&token,1, MPI_INT, MPI_ANY_SOURCE, TAG_TOKEN_CYRCLE, MPI_COMM_WORLD, &status);
				cout << *my_rank << ": Recieved token color=" << token << "\n";
				int destination;
				if( *my_rank == 0 ) {
					if (token == TOKEN_START) {
						token = TOKEN_WHITE;
						destination = 1;
						cout << *my_rank << ": Sending token color=" << token << " to process=" << destination << "\n";
						MPI_Send(&token, 1, MPI_INT, destination, TAG_TOKEN_CYRCLE, MPI_COMM_WORLD);
					}
					else {
						if (token == TOKEN_WHITE) {
							for (int dest = 1; dest < *p; ++dest) {
								MPI_Send(0, 0, MPI_INT, dest , TAG_FINISH, MPI_COMM_WORLD);
							}
							return true;
						}
					}
				}
				else
				{
					if (stack->size() > 0) {
						token = TOKEN_BLACK;
					}
					destination = (*my_rank + 1) % *p;
					cout << *my_rank << ": Sending token color=" << token << " to process=" << destination << "\n";
					MPI_Send(&token, 1, MPI_INT, destination , TAG_TOKEN_CYRCLE, MPI_COMM_WORLD);
				}
				break;
			case TAG_FINISH:
				MPI_Recv(0, 0, MPI_INT, source, TAG_FINISH, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
				return true;
				break;
			default:
				cout << "INVALID TAG!";
				//TODO: Špatný tag!!!
				break;
			}
		}
	} while (stack->size()==0 || flag);
	return false;
}

void doSearch(vector< vector<int> > *stack, Graph *graph, int *level, vector<int> *result, int *p, int *my_rank) {
	int dimension = graph->size;
	bool done = false;

	while (!done) {
		//hlavni cyklus, prochazi zasobnik
		int cycleCounter = 0;
		while (stack->size()>0) {
			if (SLOWDOWN) {
				usleep(10000*(*my_rank + 1));
			}
			vector<int> partialResult = stack->back();
			stack->pop_back();
			printVector(partialResult,"Trying: ", *my_rank);
			cout << *my_rank << ": stack size=" << stack->size() << "\n";
			//otestuj castecne reseni
			if ((partialResult.size() < dimension) && testPartialResult(partialResult, graph, *level)) {
				*result = partialResult;
				printVector(partialResult,"Solution found : ", *my_rank);
				dimension = result->size();
				for (int var = 0; var < *p; ++var) {
					if (var != *my_rank) {
						MPI_Send(&dimension, 1, MPI_INT, var, TAG_NEW_DIMENSION, MPI_COMM_WORLD);
					}
				}
			}
			else if (partialResult.size() < (dimension - 1)) {
				//expanduj castecne reseni tehdy ma-li to smysl
				expandStack(expandPartialResult(partialResult, graph), *stack);
				if (VERBOSE) {
					printVector(partialResult,"Expanding: ", *my_rank);
				}
			}

			if ((cycleCounter % CHECK_MSG_AMOUNT) == 0) {
				checkMessages(stack, graph, &dimension, my_rank, p);
			}
			cycleCounter++;
		}
		int next = (*my_rank + 1) % *p;
		MPI_Send(0, 0, MPI_INT, next, TAG_WORK_REQUEST, MPI_COMM_WORLD);
		done = checkMessages(stack, graph, &dimension, my_rank, p);
		cout << *my_rank << ": Search finished\n";
	}
}

int main(int argc, char *argv[]) {
	Graph graph;
	int level;
	int my_rank;
	int p;

	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
	MPI_Comm_size(MPI_COMM_WORLD, &p);

	if (!init(&argc, argv, &graph, &level)) {
		cout << "[-v] <graph_file> <i>\n";
		return -1;
	}
	else {

		cout << "Graph loaded.\n";
		cout << "Graph size: " << graph.size << "\n";
		cout << "i = " << level << "\n\n";
		if (graph.size < p) {
			cout << "Too many processes!\n";
			return -1;
		}


		double t1, t2;
		/* time measuring - start */
		t1 = MPI_Wtime();

		vector< vector<int> > stack;
		vector<int> result(graph.size + 1);

		initStack(&stack, graph.size, p, my_rank);

		MPI_Barrier(MPI_COMM_WORLD);

		doSearch(&stack, &graph, &level, &result, &p, &my_rank);

		MPI_Barrier(MPI_COMM_WORLD);

		int myBestSize = result.size();
		int allBestSize;
		cout << my_rank << ":  getting minimum solution size (my size=" << myBestSize << ")\n";
		MPI_Reduce(&myBestSize, &allBestSize, 1, MPI_INT, MPI_MIN, 0, MPI_COMM_WORLD);
		cout << my_rank << ":  minimum solution size=" << allBestSize << "\n";

		MPI_Barrier(MPI_COMM_WORLD);

		if (my_rank==0) {
			int *bestSolution;
			if (myBestSize == allBestSize) {
				cout << my_rank << ": Has one of the best solutions!\n";
				bestSolution = result.data();
				for (int var = 1; var < p; ++var) {
					cout << my_rank << ": Sending to " << var << " imposible request\n";
					int msg = allBestSize - 1;
					MPI_Send(&msg, 1, MPI_INT, var, TAG_BEST_REQUEST, MPI_COMM_WORLD);
				}
			}
			else {
				for (int var = 1; var < p; ++var) {
					cout << my_rank << ": Requesting best solution from process=" << var << "\n";
					MPI_Send(&allBestSize, 1, MPI_INT, var, TAG_BEST_REQUEST, MPI_COMM_WORLD);
				}
				cout << my_rank << ": Waiting for any best solution\n";
				int flag;
				MPI_Status status;
				bool haveBestSolution = false;
				do {
					flag = 0;
					MPI_Iprobe(MPI_ANY_SOURCE, TAG_BEST_SENT, MPI_COMM_WORLD, &flag, &status);
					if (flag)
					{
						if (status.MPI_TAG == TAG_BEST_SENT) {
							MPI_Recv(&bestSolution, allBestSize, MPI_INT, status.MPI_SOURCE, TAG_BEST_SENT, MPI_COMM_WORLD, &status);
							haveBestSolution = true;
						}
					}
				} while (!haveBestSolution);

				cout << my_rank << ": Best solution recieved from "  << status.MPI_SOURCE << "\n";
			}
			cout << "\nOne of the best solutions: (";
			for (int var = 0; var < allBestSize - 1; ++var) {
				cout << bestSolution[var] << ", ";
			}
			cout << bestSolution[allBestSize - 1] << ")\n";
			cout << "Size of best solution: " << allBestSize << "\n";
		}
		else {
			MPI_Request request;
			cout << my_rank << ": Waiting request for best solution\n";
			MPI_Recv(&allBestSize, 1, MPI_INT, 0, TAG_BEST_REQUEST, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
			if (allBestSize == result.size()) {
				int* bestSolution;
				bestSolution = result.data();
				cout << "\nOne of the best solutions (by process=" << my_rank << "): (";
				for (int var = 0; var < allBestSize - 1; ++var) {
					cout << bestSolution[var] << ", ";
				}
				cout << bestSolution[allBestSize - 1] << ")\n";
				cout << "Size of best solution: " << allBestSize << "\n";
				MPI_Send(bestSolution, result.size(), MPI_INT, 0, TAG_BEST_SENT, MPI_COMM_WORLD);
				cout << my_rank << ": Sent solution\n";
			}
		}

		MPI_Barrier(MPI_COMM_WORLD);

		/* time measuring - stop */
		t2 = MPI_Wtime();

		printf ("%d: Elapsed time is %f.\n",my_rank,t2-t1);

	}
	MPI_Finalize();
	return 0;
}

